#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <error.h>

#include "graph.h"
#include "queue.h"

pGraph initGraph(int capacity) {
	pGraph graph = malloc(sizeof(struct Graph));
	graph->capacity = capacity;
	graph->nVertex = 0;
	graph->vertexList = malloc(sizeof(pVertex) * capacity);
	return graph;
}

pVertex createVertex(uint id) {
	pVertex vertex = malloc(sizeof(struct Vertex));
	if (vertex == NULL) perror("out of space");
	vertex->id = id;
	vertex->edge = NULL;
	vertex->inDegree = 0;
	return vertex;
}

pEdge createEdge(uint id, float weight) {
	pEdge edge = malloc(sizeof(struct Edge));
	if (edge == NULL) perror("out of space");
	edge->id = id;
	edge->weight = weight;
	edge->next = NULL;
	return edge;
}

pVertex findVertex(pGraph graph, uint id) {
	pVertex target = NULL;
	int i = 0;
	for (i = 0; i < graph->nVertex; i++) {
		pVertex node = graph->vertexList[i];
		if (node->id == id) {
			target = node;
			break;
		}
	}
	return target;
}

void addVertex(pGraph graph, uint id) {
	if (graph->nVertex == graph->capacity) {
		printf("graph full");
		return;
	}
	if (findVertex(graph, id) != NULL) {
		printf("[x] error : addVertex, exists id=%d\n", id);
		return;
	}

	graph->vertexList[graph->nVertex] = createVertex(id);
	graph->nVertex ++;
}

void printGraph(pGraph graph) {
	pVertex vertex;
	int count = 0;
	int i = 0;
	for (i = 0; i < graph->nVertex; i++) {
		vertex = graph->vertexList[i];
		printVertex(vertex);
	}
}


void printVertex(pVertex vertex) {
	if (vertex != NULL) {
		printf("id=%d, in=%d  ", vertex->id, vertex->inDegree);
	}
	pEdge edge = vertex->edge;
	printf("edges: ");
	while (edge != NULL) {
		printf("[id=%d, w=%.1f], ", edge->id, edge->weight);
		edge = edge->next;
	}
	printf("\n");
}


void addEdge(pGraph graph, uint id1, uint id2, float weight) {
	// find the id1 node
	pVertex vertex1 = findVertex(graph, id1);
	if (vertex1 == NULL) {
		printf("[x] error: addEdge, id %d not found", id1);
		return;
	}
	pVertex vertex2 = findVertex(graph, id2);
	if (vertex2 == NULL) {
		printf("[x] error: addEdge, id %d not found", id2);
		return;
	}

	pEdge edge = vertex1->edge;
	if (edge == NULL) {
		vertex1->edge = createEdge(id2, weight);
		vertex2->inDegree ++;
	} else {
		pEdge preEdge = edge;
		while (edge != NULL) {
			if (edge->id == id2) {
				printf("[x] error: addEdge, edge exists (%d->%d)\n", id1, id2);
				return;
			}
			preEdge = edge;
			edge = edge->next;
		}
		preEdge->next = createEdge(id2, weight);
		vertex2->inDegree ++;
	}
}

void dropVertex(pGraph graph, uint id) {
	pVertex vertex;
	int i = 0;
	for (i = 0; i < graph->nVertex; i++) {
		pVertex node = graph->vertexList[i];
		if (node->id == id) {
			vertex = node;
			break;
		}
	}

	if (vertex == NULL) {
		printf("[x] error: dropVertex, id %d not found", id);
		return;
	}

	pEdge edge = vertex->edge;
	graph->vertexList[i] = graph->vertexList[graph->nVertex - 1];
	graph->vertexList[graph->nVertex - 1] = NULL;
	free(vertex);
	graph->nVertex --;

	// handle id->xx
	while (edge != NULL) {
		int did = edge->id;
		pVertex toVertex = findVertex(graph, did);
		if (toVertex != NULL)toVertex->inDegree --;
		edge = edge->next;
	}

	// handle xx->id
	for (i = 0; i < graph->nVertex; i++) {
		vertex = graph->vertexList[i];
		edge = vertex->edge;
		if (edge == NULL) continue;

		// first edge ->id
		if (edge->id == id) {
			vertex->edge = edge->next;
			free(edge);
			continue;
		}

		while (edge->next != NULL) {
			if (edge->next->id == id) {
				pEdge tmp = edge->next;
				edge->next = tmp->next;
				free(tmp);
				break;
			}
			edge = edge->next;
		}
	}
}

pVertex findZeroInDegree(pGraph graph) {
	pVertex target = NULL;
	int i, count;
	for (i = 0, count = 0; i < graph->nVertex; i++ ) {
		pVertex node = graph->vertexList[i];
		count++;
		if (node->inDegree == 0) {
			target = node;
			break;
		}
	}
	return target;
}

void topSort(pGraph graph) {
	// store current inDegree status
	int i;
	int *store = malloc(sizeof(int) * graph->nVertex);
	for (i = 0; i < graph->nVertex; i++) {
		store[i] = graph->vertexList[i]->inDegree;
	}

	// handle, will modify v->inDegree
	Queue queue = createQueue(graph->nVertex);
	Queue q2 = createQueue(graph->nVertex);

	pVertex vertex;
	for (i = 0; i < graph->nVertex; i++) {
		vertex = graph->vertexList[i];
		if (vertex->inDegree == 0) {
			enQueue(queue, vertex->id);
		}
	}

	while (!isEmpty(queue)) {
		int vid = deQueue(queue);
		enQueue(q2, vid);
		vertex = findVertex(graph, vid);
		pEdge edge = vertex->edge;
		// all w adjacent to v
		while (edge != NULL) {
			if (--findVertex(graph, edge->id)->inDegree == 0)
				enQueue(queue, edge->id);
			edge = edge->next;
		}
	}
	if (!isFull(q2)) {
		printf("[x] error: topSort has circle. \n");
	} else {
		while (!isEmpty(q2)) {
			printf("%d-> ", deQueue(q2));
		}
		printf("End\n");
	}
	disposeQueue(queue);
	disposeQueue(q2);

	// restore current status
	for (i = 0; i < graph->nVertex; i++) {
		graph->vertexList[i]->inDegree = store[i] ;
	}
}


void unWeightShortPath(pGraph graph, uint fromId) {
	Queue queue = createQueue(graph->nVertex);
	struct assist {
		int id;
		int known ;
		int dist;
		int preId;
	};

	struct assist *list = malloc(sizeof(struct assist) * graph->nVertex);
	int found = 0;
	int i;
	for (i = 1; i < graph->nVertex; i++) {
		list[i].id = -1;
		list[i].known = 0;
		list[i].dist = -1;
		list[i].preId = -1;
	}
	list[found].id = fromId;
	list[found].known = 1;
	list[found].dist = 0;
	list[found].preId = fromId;
	found ++;
	enQueue(queue, fromId);

	//
	while (!isEmpty(queue)) {
		int id = deQueue(queue);
		pVertex vertex = NULL;
		for (i = 0; i < graph->nVertex; i++) {
			if ( graph->vertexList[i] ->id == id) {
				vertex = graph->vertexList[i];
				break;
			}
		}

		struct assist tmp ;
		for (i = 0; i < found; i++) {
			if (list[i].id == vertex->id) {
				tmp = list[i];
				break;
			}
		}

		// find w adjacent to vertex
		pEdge edge = vertex->edge;
		while (edge != NULL) {
			int id2 = edge->id;
			// if id2 known
			int known = 0;
			for (i = 0; i < found; i++) {
				if (list[i].id == id2) {known = 1; break;}
			}
			if (!known) {
				list[found].id = id2;
				list[found].known = 1;
				list[found].dist = tmp.dist + 1;
				list[found].preId = vertex->id;
				found ++;
				enQueue(queue, id2);
			}
			edge = edge->next;
		}
	}

	// print result
	for (i = 0; i < found; i++) {
		struct assist tmp  = list[i];
		printf("%2d -> %2d, min length =%2d, preId=%2d\n", fromId, tmp.id, tmp.dist, tmp.preId);
	}
	free(list);

	//
	disposeQueue(queue);
}

void weightShortPath(pGraph graph, uint fromId) {
	struct assist {
		int id;
		int known ;
		int dist;
		int preId;
	};
	struct assist **ukList = malloc(sizeof(struct assist*) * graph->nVertex);
	struct assist **knList = malloc(sizeof(struct assist*) * graph->nVertex);
	int knSize = 0; // known node, empty position
	int ukSize = 0; // known node, empty position
	int i;
	for (i = 1; i < graph->nVertex; i++) {
		ukList[i] = NULL;
		knList[i] = NULL;
	}

	// self
	knList[knSize] = malloc(sizeof(struct assist));
	knList[knSize]->id = fromId;
	knList[knSize]->dist = 0;
	knList[knSize]->preId = fromId;
	knSize++;

	pEdge edge = findVertex(graph, fromId)->edge;
	while (edge != NULL) {
		ukList[ukSize] = malloc(sizeof(struct assist));
		printf("unknown,id=%d\n", edge->id);
		ukList[ukSize]->id = edge->id;
		ukList[ukSize]->dist = edge->weight;
		ukList[ukSize]->preId = fromId;
		//
		ukSize ++;
		edge = edge->next;
	}
	while (ukSize > 0) {
		int min = ukList[0]->dist;
		int j = 0;
		for (i = 1; i < ukSize; i++) {
			if (min > ukList[i]->dist) j = i;
		}

		// j, unknown => known
		printf("[x]known,id=%d\n", ukList[j]->id);
		struct assist* thisMin = ukList[j];
		thisMin->known = 1;
		knList[knSize++] = thisMin;
		if (ukSize == 1) {
			ukList[j] = NULL;
			ukSize --;
			break; // last one
		}

		ukList[j] = ukList[ukSize - 1];
		ukList[ukSize - 1] = NULL;
		ukSize --;

		// add adjacent of j
		pEdge edge = findVertex(graph, thisMin->id)->edge;
		while (edge != NULL) {
			int id = edge->id;
			int preDist = -1;
			for (i = 0; i < ukSize; i++) {
				if (ukList[i]->id == id) {
					preDist = ukList[i]->dist;
					break;
				}
			}

			int newDist = edge->weight + thisMin->dist;
			if (preDist > 0) {
				if (newDist < preDist) {
					printf("update unknown,id=%d\n", id);
					ukList[i]->id = id;
					ukList[i]-> preId = thisMin->id;
					ukList[i]-> dist = newDist;
				}
			} else {
				int known = 0;
				int m;
				for (m = 0; m < knSize; m++) {
					if (knList[m]->id == id) {
						known = 1;
						break;
					}
				}
				if (!known) {
					printf("unknown,id=%d\n", id);
					ukList[ukSize] = malloc(sizeof(struct assist));
					ukList[ukSize]->id = id;
					ukList[ukSize]->dist = newDist;
					ukList[ukSize]->preId = thisMin->id;
					ukSize ++;
				}
			}
			edge = edge->next;
		}
	}

	// print result
	for (i = 0; i < knSize; i++) {
		struct assist* thisMin = knList[i];
		printf("%d -> %d, len=%d, preId=%d \n", fromId, thisMin->id, thisMin->dist, thisMin->preId);
	}


	printf("unknown size=%d\n", ukSize);
	for (i = 0; i < ukSize; i++) {
		if (ukList[i]->known == 1) { printf("known node in ukList id=%d\n", ukList[i]->id);}
		free(ukList[i]);
	}
	free(ukList);

	// clean up
	printf("known size=%d\n", knSize);
	for (i = 0; i < knSize; i++) {
		free(knList[i]);
	}
	free(knList);


}